package com.li.list;

import java.util.LinkedHashMap;

public class ListDemo {
	public static void main(String[] args) {
		Node head = buildList();
		//		printList(head);
		//		reverse(head);
		//		printList(head);
		//		System.out.println(isHasCircle(head));
//		reverse(head);
//		printList(head);
//		head = sortList(head);
		printList(head);
//		System.out.println(getKthNode(head, 3).value);
//		deleteKthNode(head, 3);
//		printList(head);
		//deleteRepeat2(head);
		//rotateList(head, 4);
		reverseListBetweenMAndN(head, 2, 4);
		printList(head);
	}



	public static Node buildList(){
		Node head = new Node();
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);

		head.next = node1;
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		return head;
	}
	
	public static Node buildList2(){
		Node head = new Node();
		Node node1 = new Node(1);
		Node node11 = new Node(1);
		Node node3 = new Node(3);
		Node node33 = new Node(3);
		Node node5 = new Node(5);
		Node node6 = new Node(6);

		head.next = node3;
		node3.next = node1;
		node1.next = node11;
		node11.next = node33;
		node33.next = node6;
		node6.next = node5;
		return head;
	}

	/**
	 * 打印链表
	 * @param head
	 */
	public static void printList(Node head){
		while((head = head.next)!=null){
			System.out.print(head.value+" ");
		}
		System.out.println();
	}

	/**
	 * 翻转链表
	 * @param head
	 * @return
	 */
	public static Node reverse(Node head){
		if(head == null || head.next ==null){
			return 	head;
		}
		Node node  = head.next;
		Node temp = null;
		Node pre = null;
		while(node != null){
			temp = node.next;
			node.next = pre;
			pre = node;
			node = temp;
		}
		head.next = pre;
		return head;
	}

	/**
	 * 判断链表是否有环
	 * @param head
	 * @return
	 */
	public static boolean isHasCircle(Node head){
		if(head == null || head.next ==null){
			return false;
		}
		Node fast = head.next;
		Node slow = head;
		while(fast!=slow){
			if(fast == null || fast.next ==null){
				return false;
			}
			fast = fast.next.next;
			slow = slow.next;
		}
		return true;
	}
	/**
	 * 链表排序,采用归并排序的方式
	 * @param head
	 * @return
	 */
	public static Node sortList(Node head){
		if(head == null || head.next == null){
			return head;
		}
		Node mid = getMidNode(head);
		Node right = sortList(mid.next);
		mid.next = null;
		Node left = sortList(head);
		return merge(left,right);
	}

	public static Node merge(Node left, Node right) {
		Node head = new Node();
		Node node = head;
		while(left!=null && right!=null){
			if(left.value <right.value){
				node.next = left;
				left = left.next;
			}else{
				node.next = right;
				right = right.next;
			}
			node = node.next;
		}
		if(left!=null){
			node.next = left;
		}else{
			node.next = right;
		}
		return head.next;
	}

	public static Node getMidNode(Node head) {
		if(head == null || head.next ==null){
			return head;
		}
		Node fast = head.next;
		Node slow = head;
		while(fast!=null && fast.next!=null){
			fast = fast.next.next;
			slow = slow.next;
		}
		return slow;
	}
	
	/**
	 * 获取倒数第k个节点
	 * @param head
	 * @param k
	 * @return
	 */
	public static Node getKthNode(Node head, int k){
		if(head == null || head.next == null){
			return head;
		}
		Node node1 = head;
		Node node2 = head;
		for(int i = 0;i < k;i++){
			if(node1 == null){
				return null;
			}
			node1 = node1.next;
		}
		while(node1!=null){
			node1 = node1.next;
			node2 = node2.next;
		}
		return node2;
	}
	
	/**
	 * 删除倒数第k个节点
	 * @param head
	 * @param k
	 * @return
	 */
	public static Node deleteKthNode(Node head, int k){
		if(head == null || head.next == null){
			return head;
		}
		Node node1 = head;
		Node node2 = head;
		for(int i = 0;i <= k;i++){
			if(node1 == null){
				return null;
			}
			node1 = node1.next;
		}
		while(node1!=null){
			node1 = node1.next;
			node2 = node2.next;
		}
		node2.next = node2.next.next;
		return head;
	}
	
	/**
	 * 删除链表中重复的节点----采用了java的linkedHashMap来去重和记录顺序
	 * @param head
	 * @return
	 */
	public static Node deleteRepeat(Node head){
		if(head == null || head.next == null){
			return head;
		}
		LinkedHashMap<Integer, Node> map = new LinkedHashMap<Integer, Node>();
		Node node = head;
		while((node = node.next)!=null){
			map.put(node.value, node);
		}
		Node pre = head;
		for(Node n : map.values()){
			pre.next = n;
			pre = n;
		}
		pre.next = null;
		return head;
	}
	
	/**
	 * 删除链表中重复的节点
	 * @param head
	 * @return
	 */
	public static Node deleteRepeat2(Node head){
		if(head == null || head.next == null){
			return head;
		}
		Node node = head.next;
		Node temp = null;
		while(node!=null){
			temp = node;
			while(temp.next!=null){
				if(node.value == temp.next.value){
					temp.next = temp.next.next;
				}
				temp = temp.next;
			}
			node = node.next;
		}
		return head;
	}
	
	/**
	 * 旋转链表
	 * @param head
	 * @param k
	 * @return
	 */
	public static Node rotateList(Node head, int k){
		if(head == null || head.next == null){
			return head;
		}
		
		Node node1 = head;
		Node node2 = head;
		
		for(int i = 0;i<k-1;i++){
			node1 = node1.next;
		}
		while(node1.next!=null){
			node1 = node1.next;
			node2 = node2.next;
		}
		node1.next = head.next;
		head.next = node2.next;
		node2.next = null;
		return head;
	}
	/**
	 * 翻转指定范围m到n的链表
	 * @param head
	 * @param m
	 * @param n
	 * @return
	 */
	public static Node reverseListBetweenMAndN(Node head,int m, int n){
		if(head == null || head.next == null){
			return head;
		}
		Node node1 = head;
		Node node2 = head;
		for(int i=0;i<m-1;i++){
			node1 = node1.next;
			node2 = node2.next;
		}
		for(int i = m-1;i<n;i++){
			node2 = node2.next;
		}
		Node pre = node1;
		Node tail = node2.next;
		
		node1 = node1.next;
		Node pre2 = tail;
		Node temp = null;
		while(node1!=null){
			temp = node1.next;
			node1.next = pre2;
			if(temp == tail){
				break;
			}
			pre2 = node1;
			node1 = temp;
		}
		pre.next = node1;
		return head;
	}
}

class Node{
	Node next;
	int value;
	public Node(int value){
		this.value = value;
	}
	public Node(){

	}
}
